//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 算法的时间复杂度应该为 O(log (m+n)) 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -10⁶ <= nums1[i], nums2[i] <= 10⁶ 
// 
//
// Related Topics 数组 二分查找 分治 👍 6499 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int m=nums1.length;
        int n=nums2.length;
        if(m>n){return findMedianSortedArrays(nums2,nums1);}
        int left=0;
        int right=m;


        while(left<=right){
            int i=(left+right)>>1;
            int j=(m+n+1)/2-i;

            if(i<right&&nums2[j-1]>nums1[i]){//如果大于num[i]，则比左边的都要大，i太小了
                left=i+1;
            } else if (i>left&&nums1[i-1]>nums2[j]) {//比右边的都要大,i太大了
                right=i-1;
            }
            else {
                int leftMax = i == 0 ? nums2[j - 1] :
                        j == 0 ? nums1[i - 1] : Math.max(nums1[i - 1], nums2[j - 1]);
                if ((m + n) % 2 == 1) {
                    return leftMax;
                }
                int rightMin = i == m ? nums2[j] :
                        j == n ? nums1[i] : Math.min(nums1[i], nums2[j]);
                return (leftMax + rightMin) / 2.0;
            }

        }
        return 0.0;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
